package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class P337HouseRobberIii {
    public static void main(String[] args) {
        Solution solution = new P337HouseRobberIii().new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(1);
        solution.rob(root);
        System.out.println(solution.val.get(root));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        public int rob1(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return rob(root, true);
        }

        Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
        Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

        public int rob(TreeNode root) {
            dfs(root);
            return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
        }

        public void dfs(TreeNode node) {
            if (node == null) {
                return;
            }
            dfs(node.left);
            dfs(node.right);
            f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
            g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
        }

        public Map<TreeNode, Integer> val = new HashMap<>();

        public int rob(TreeNode root, boolean select) {
            if (root == null) {
                return 0;
            }
            int max = 0;
            if (select) {
                max = Math.max(max, root.val + rob(root.left, false) + rob(root.right, false));
            }
            max = Math.max(max, rob(root.left, true) + rob(root.right, true));
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}